BM算法

from pwn import *  
import numpy as np  
from tqdm import tqdm  
  
HOST = "bruh.chal.ctf.ae"  
r = remote(HOST, 443, ssl=True, sni=HOST)  
  
def get_sample_gata(guess):  
    r.sendlineafter(b"> (str)", guess)  
    r.recvuntil(b"RETURN = ")  
    sample_data = int(r.recvline().strip())  
    return sample_data  
  
# I know lfsr_flag ^ lfsr_guess = sample_data  
# send \x00 * 38 to get the output of only lfsr_flag  
  
# get sample_data  
guess = b'\x00' * 38  
sample_data = get_sample_gata(guess)  
print("Sample data: ", sample_data)  
sample_data = [int(i) for i in bin(sample_data)[2:].zfill(640)]  
  
  
def Berlekamp_Massey_algorithm(sequence):  
    N = len(sequence)  
    s = sequence[:]  
  
    for k in range(N):  
        if s[k] == 1:  
            break  
    f = set([k + 1, 0])  # use a set to denote polynomial  
    l = k + 1  
  
    g = set([0])  
    a = k  
    b = 0  
  
    for n in range(k + 1, N):  
        d = 0  
        for ele in f:  
            d ^= s[ele + n - l]  
  
        if d == 0:  
            b += 1  
        else:  
            if 2 * l > n:  
                f ^= set([a - b + ele for ele in g])  
                b += 1  
            else:  
                temp = f.copy()  
                f = set([b - a + ele for ele in f]) ^ g  
                l = n + 1 - l  
                g = temp  
                a = b  
                b = n - l + 1  
  
    # output the polynomial  
    def print_poly(polynomial):  
        result = ''  
        lis = sorted(polynomial, reverse=True)  
        for i in lis:  
            if i == 0:  
                result += '1'  
            else:  
                result += 'x^%s' % str(i)  
  
            if i != lis[-1]:  
                result += ' + '  
  
        return result  
  
    # return (print_poly(f), l)  
    # return the coefficients of the polynomial  
    f = [x - 1 for x in f if x != 0]  
    return list(f)  
  
taps = Berlekamp_Massey_algorithm(sample_data)  
print("Got taps:", taps)  
  
class LFSR:  
    def __init__(self, state: bytes, taps):  
        # self.state = [int(i) for i in '{:0{n}b}'.format(int.from_bytes(seed, 'big'), n=8*len(seed))]  
        self.taps = taps  
        self.state = state  
  
    def Run(self, k: int = 1):  
        out = []  
        for _ in range(k):  
            new = 0  
            for tap in self.taps:  
                new ^= self.state[tap]  
            out.append(self.state[-1])  
            self.state = [new] + self.state[:-1]  
        return out  
      
from z3 import *  
flag_state = [BitVec(f"state_{i}", 1) for i in range(38 * 8)]  
  
sample_data = sample_data[::-1]  
s = Solver()  
lfsr_flag = LFSR(flag_state, taps)  
print(len(sample_data))  
for i in range(2 ** 7 + 2 ** 9 - 1):  
    s.add(lfsr_flag.Run()[0] == int(sample_data[i]))  
  
def reverse_one_step(lfsr_state):  
    flag_state = [BitVec(f"state_{i}", 1) for i in range(38 * 8)]  
    lfsr_flag = LFSR(flag_state, taps)  
    lfsr_flag.Run(1)  
    s = Solver()  
    for i in range(38 * 8):  
        s.add(lfsr_flag.state[i] == lfsr_state[i])  
    if s.check() == sat:  
        m = s.model()  
        return [m[state].as_long() for state in flag_state]  
    return None  
  
  
while s.check() == sat:  
    model = s.model()  
    lfsr_state = [model[state].as_long() for state in flag_state]  
    # now reverse 1337 steps to get the flag  
    lfsr = LFSR(lfsr_state, taps)  
    for i in tqdm(range(1337)):  
        lfsr.state = reverse_one_step(lfsr.state)  
    flag = bytes([int(''.join(map(str, lfsr.state[i:i+8])), 2) for i in range(0, 38 * 8, 8)])  
    print(flag)  
    exit()
 

用BM算法求解lfsr的反馈多项式是极好的